import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

import javax.annotation.PreDestroy;

class Vertex {
	private List<Edge> outGoingEdges;
	private String data;
	private boolean visited;
	
	public Vertex(String data) {
		this.data = data;
	}
	
	public String getData() {
		return data;
	}
	
	public boolean addEdge(Edge e) {
		if(e.getStart() == this) {
			outGoingEdges.add(e);
			return true;
		}
		return false;
	}
	
	public boolean removeEdge(Edge e) {
		return outGoingEdges.remove(e);
	}
	
	public List<Edge> getOutGoingEdges() {
		return outGoingEdges;
	}
	
	public Edge findEdge(Vertex end) {
		for(Edge edge : outGoingEdges) {
			if(edge.getEnd() == end) {
				return edge;
			}
		}
		return null;
	}
	
	public void visited() {
		visited = true;
	}
	
	public void clearVisited() {
		visited = false;
	}
	
	public boolean isVisited() {
		return visited;
	}
}

class Edge {
	Vertex start, end;
	int weight;
	public Edge(Vertex start, Vertex end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	
	public Vertex getStart() {
		return start;
	}
	
	public Vertex getEnd() {
		return end;
	}
	
	public int getWeight() {
		return weight;
	}
}

public class DirectedGraph {
	List<Vertex> vertices;
	List<Edge> edges;
	Vertex rootVertex;
	
	public DirectedGraph() {
		vertices = new ArrayList<Vertex>();
		edges = new ArrayList<Edge>();
	}
	
	public boolean addVertex(Vertex v) {
		boolean added = false;
		if(vertices.contains(v) == false) {
			added = vertices.add(v);
		}
		return added;
	}
	
	public int size() {
		return vertices.size();
	}
	
	public void setRootVertex(Vertex v) {
		rootVertex = v;
	}
	
	public List<Vertex> getVertices() {
		return vertices;
	}
	
	public List<Edge> getEdges() {
		return edges;
	}
	
	public Vertex getVertex(int n) {
		return vertices.get(n);
	}
	
	public boolean addEdge(Vertex start, Vertex end, int weight) throws IllegalArgumentException {
		if(vertices.contains(start) == false) {
			throw new IllegalArgumentException("Start vertex not in graph");
		}
		if(vertices.contains(end) == false) {
			throw new IllegalArgumentException("End vertex not in graph");
		}
		Edge e = new Edge(start, end, weight);
		if(start.findEdge(end) != null || edges.contains(e) != false) {
			return false;
		}else {
			start.addEdge(e);
			edges.add(e);
			return true;
		}
	}
	
	public boolean removeEdge(Vertex start, Vertex end) {
		if(start.findEdge(end) == null) {
			return false;
		} else {
			Edge e = start.findEdge(end);
			start.removeEdge(e);
			edges.remove(e);
			return true;
		}
	}
	
	public void clearVisited() {
		for(Vertex v : vertices) {
			v.clearVisited();
		}
	}
	
 	public boolean depthFirstSearch(String toFind, Vertex currVertex) {
		if(currVertex.getData().equals(toFind)) {
			clearVisited();
			return true;
		}
		if (currVertex.isVisited() == false) {
			currVertex.visited();
			List<Edge> outGoingEdges = currVertex.getOutGoingEdges(); 
			for(int i = 0; i < outGoingEdges.size(); i++) {
				Edge e = outGoingEdges.get(i);
				depthFirstSearch(toFind, e.getEnd());
			}
		}
		clearVisited();
		return false;
	}
	
	public int shortestPath(Vertex start, Vertex end) {
		int cost = 0;
		ShortestPathExecutor executor = new ShortestPathExecutor(this, start, end);
		cost = executor.execute();
		return cost;
	}
	
	public int directPath(Vertex start, Vertex end) {
		if(start.findEdge(end) != null) {
			return start.findEdge(end).getWeight();
		}
		return Integer.MAX_VALUE;
	}
}

class ShortestPathExecutor {
	DirectedGraph g;
	Vertex start, end;
	private Set<Vertex> settledNodes = new HashSet<Vertex>();
	private Map<Vertex, Integer> shortestDistances = new HashMap<Vertex, Integer>();
	private Map<Vertex, Vertex> predecessors = new HashMap<Vertex, Vertex>();
	private PriorityQueue<Vertex> unsettledNodes;
	
	private final static int INFINITE_DISTANCE = Integer.MAX_VALUE;
	
	public ShortestPathExecutor(DirectedGraph g, Vertex start, Vertex end) {
		this.g = g;
		this.start = start;
		this.end = end;
		unsettledNodes = new PriorityQueue<Vertex>(g.size(), shortestDistanceComparator);
	}
	
	private void init() {
		settledNodes.clear();
		shortestDistances.clear();
		predecessors.clear();
		unsettledNodes.clear();
	}
	
	private int getShortestDistance(Vertex v) {
		return shortestDistances.get(v) == null ? INFINITE_DISTANCE : shortestDistances.get(v);
	}
	
	private Vertex getMinVertex() {
		return unsettledNodes.poll();
	}
	
	private boolean isSettled(Vertex v) {
		return settledNodes.contains(v);
	}
	
	private Comparator<Vertex> shortestDistanceComparator = new Comparator<Vertex>() {

		@Override
		public int compare(Vertex o1, Vertex o2) {
			int shortestDistanceLeft = getShortestDistance(o1);
			int shortestDistanceRight = getShortestDistance(o2);
			
			if(shortestDistanceLeft < shortestDistanceRight) {
				return -1;
			} else if (shortestDistanceLeft > shortestDistanceRight) {
				return 1;
			}
			return 0;
		}
	};
	
	public void setShortestDistance(Vertex v, int distance) {
		unsettledNodes.remove(v);
		shortestDistances.put(v, distance);
		unsettledNodes.add(v);
	}
	
	public void setPredesessor(Vertex predesessor, Vertex currVertex) {
		predecessors.put(currVertex, predesessor);
	}
	
	public Vertex getPredesessor(Vertex v) {
		return predecessors.get(v);
	}
	
	public void relaxNeighbors(Vertex v) {
		for(Edge e : v.getOutGoingEdges()) {
			Vertex toVertex = e.getEnd();
			if(isSettled(toVertex)) {
				continue;
			}
			int shortestDistance = getShortestDistance(v) + g.directPath(v, toVertex);
			if(shortestDistance < getShortestDistance(toVertex)) {
				setShortestDistance(toVertex, shortestDistance);
				setPredesessor(v, toVertex);
			}
		}
	}
	
	public int execute() {
		init();
		while(!unsettledNodes.isEmpty()) {
			Vertex minVertex = getMinVertex();
			if(end == minVertex) {
				return getShortestDistance(end);
			}
			
			settledNodes.add(minVertex);
			relaxNeighbors(minVertex);
		}
		return 0;
	}
}